package sf;
/*https://www.cnblogs.com/mengfanrong/p/4210574.html
*/
public class SingleLinkedList <T>{
	private int size;//节点的个数
	private Node<T> head;//头结点
	
	public SingleLinkedList() {
		this.size = 0;
		this.head = null;
	}
	private class Node<T>{
		private T data;//节点数据
		private Node next;//每个节点指向下一个节点的连接	
		public Node(T data) {
			this.data = data;
		}
	}
	public T addHead(T data) {
		//每次插入的新节点作为头节点
		Node newHead = new Node<T>(data);
		if (size == 0) {
			this.head = newHead;			
		}else {
			newHead.next = this.head;//当前节点的下一个节点为之前的节点
			this.head = newHead;//设置head为插入的node
		}
		size++;
		return data;
	}
	
	public T deleteHead() {
		if (size == 0)
			return null;
		T data = this.head.data;
		this.head = this.head.next;//新头结点为头结点的下一个节点
		size --;
		return data;
	}
	
	public Node find(T data) {
		Node current = this.head;
		int tempSize = size;
		while(tempSize>0) {
			if (data.equals(current.data))
				return current;
			else 
				current = current.next;//往下搜索
			tempSize--;
		}
		return null;
	}
	
	public boolean delete(T data) {
		if (size == 0) 
			return false;
		Node cureent = this.head;
		Node previous = this.head;
		while(!data.equals(cureent.data)) {//找到则跳出
			if (cureent.next == null) {//说明遍历到了尾节点
				return false;
			}else {//继续往下搜索
				previous = cureent;//2向下位移一位，所以该节点的上一个节点
				cureent = cureent.next;//2
			}
		}
		if (cureent == this.head) {
			this.head = cureent.next;
			size--;
		}else {
			previous.next = cureent.next;
			size--;
		}
		return true;
	}
	
	public boolean isEmpty() {
		return size==0;
	}
	
	 //显示节点信息
    public void display(){
        if(size >0){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){//当前链表只有一个节点
                System.out.println("["+node.data+"]");
                return;
            }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.data+"->");
                }else if(node.next == null){
                    System.out.print(node.data+"]");
                }else{
                    System.out.print(node.data+"->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        }else{//如果链表一个节点都没有，直接打印[]
            System.out.println("[]");
        }
        
    }
    public static void main(String[] args) {
		SingleLinkedList<String> sList = new SingleLinkedList<>();
		sList.addHead("A");
		sList.addHead("B");
		sList.addHead("C");
		sList.display();
		sList.delete("C");
		
		sList.display();
	}
}
